/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
  let flag = false, res = [];
  // 深搜
  function dfs(n) {
    // 判断上一个数据是否满足条件（ 横、竖、九宫格 ）
    if (n > 0 && n <= 81) {
      // 如果不合法，就直接结束
      if (!isReasonable(n - 1)) return;
    }

    if (n >= 81) {//　到最后则返回
      flag = true;
      res = [...board];
      return;
    }

    let x = Math.floor(n / 9); // 定位当前数的位置
    let y = n % 9;
    if (board[x][y] != '.') // 只对 数字为 0 的元素进行搜索
      dfs(n + 1);
    else {
      // 每一个空位有 9 种可能性
      for (let i = 1; i < 10; i++) {
        board[x][y] = i + ''; // 当前的数字放入到数组之中，
        dfs(n + 1); // 进行下一个位置的搜索
        if (flag == true) return;
        board[x][y] = '.'; // 不满足条件，重新清 0
      }
    }
  }

  function isReasonable(n) { // n 表示是数独81个数字当中，当前为第几个数
    let x = Math.floor(n / 9); // 定位当前数的位置（数据在二维数组中的位置）
    let y = n % 9;
    for (let i = 0; i < 9; i++) {// 横竖 搜索
      if (board[x][i] == board[x][y] && i != y) return false;
      if (board[i][y] == board[x][y] && i != x) return false;
    }

    // 九宫格 搜索	这里需要一个小小的算法，确定九宫格的位置
    for (let i = Math.floor(x / 3) * 3; i < Math.floor(x / 3) * 3 + 3; i++)
      for (let j = Math.floor(y / 3) * 3; j < Math.floor(y / 3) * 3 + 3; j++)
        if (board[i][j] == board[x][y] && (i != x || j != y))
          return false;
    return true;
  }

  dfs(0);
  return res;
};
let board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
console.log(solveSudoku(board));
board = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"]
]
console.log(solveSudoku(board));
